#pragma once

#include "stdafx.h"
#include <Windows.h>
#include <cstdio>
#include <tchar.h>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
template<typename T>
struct TreeNode
{
	T Data;
	TreeNode<T>* pLeftNode;
	TreeNode<T>* pRightNode;
};


template<typename T>
class CBinTree
{
public:
	CBinTree();
	CBinTree(const T ary[], int nCount);
	~CBinTree();

public:
	void CreateNode(TreeNode<T>* pNode, const T& Data);
	void CreateBinTree(TreeNode<T>*& pNode, const T ary[], int nCount);
	void DestroyBinTree(TreeNode<T>*& pNode);
	void InorderTraversal(bool bRecursion = true);
	void InorderTraversal(TreeNode<T>* pNode, bool bRecursion = true);
	void PreorderTraversal(bool bRecursion = true);
	void PreorderTraversal(TreeNode<T>* pNode, bool bRecursion = true);
	void PostorderTraversal(bool bRecursion = true);
	void PostorderTraversal(TreeNode<T>* pNode, bool bRecursion = true);
	void BreadthTravelsal();
	void BreadthTravelsal(TreeNode<T>* pNode);

	
	void PreorderTraversal(TreeNode<T>* pNode);
protected:
	inline void DoVisit(TreeNode<T>* pNode);	


protected:
	TreeNode<T>* m_pRoot;
};


template<typename T>
CBinTree<T>::CBinTree() : m_pRoot(NULL)
{

}


template<typename T>
CBinTree<T>::~CBinTree()
{
	DestroyBinTree(m_pRoot);
}


template<typename T>
CBinTree<T>::CBinTree(const T ary[], int nCount)
{
	CreateBinTree(m_pRoot, ary, nCount);	
}


template<typename T>
void CBinTree<T>::CreateBinTree(TreeNode<T>*& pNode, const T ary[], int nCount)
{
	if (nCount <= 0)
	{
		pNode = NULL;
		return;
	}
	pNode = new TreeNode<T>;
	

	pNode = (TreeNode<T>*)malloc(sizeof(TreeNode<T>));
	pNode->Data = ary[nCount/2];
	CreateBinTree(pNode->pLeftNode, ary, nCount/2);
	CreateBinTree(pNode->pRightNode, ary + nCount/2 + 1, nCount-nCount/2 -1);

}


template<typename T>
void CBinTree<T>::DestroyBinTree(TreeNode<T>*& pNode)
{
	if (NULL == pNode)
	{
		return;
	}

	TreeNode<T>* pLeftTree = pNode->pLeftNode;
	TreeNode<T>* pRightTree = pNode->pRightNode;

	// delete current tree
	delete pNode;
	pNode = NULL;

	// delete child tree recursively
	DestroyBinTree(pLeftTree);
	DestroyBinTree(pRightTree);
}

template<typename T>
inline void CBinTree<T>::DoVisit(TreeNode<T>* pNode)
{
	wcout<<pNode->Data<<L"\t";
}
template<typename T>
void CBinTree<T>::BreadthTravelsal()
{
	_tprintf_s(L"Breadth First Travel the tree:\n"); 

	BreadthTravelsal(m_pRoot);
	_tprintf_s(L"\n");
}

template<typename T>
void CBinTree<T>::BreadthTravelsal(TreeNode<T>* pNode /* = m_pRoot */)
{
	queue<TreeNode<T>*> bakQueue;
	if (NULL == pNode)
	{
		return;
	}
	bakQueue.push(pNode);
	TreeNode<T>* pCurNode = pNode;
	while (!bakQueue.empty())
	{
		bakQueue.pop();
		if (pCurNode)
		{
			DoVisit(pCurNode);
		}

		if (NULL != pCurNode->pLeftNode)
		{
			bakQueue.push(pCurNode->pLeftNode);
		}
		if (NULL != pCurNode->pRightNode)
		{
			bakQueue.push(pCurNode->pRightNode);
		}
		if (!bakQueue.empty())
		{
			pCurNode = bakQueue.front();
		}
	}

}

template<typename T>
void CBinTree<T>::InorderTraversal(bool bRecursion /*= true*/)
{
	if (bRecursion)
	{
		_tprintf_s(L"In Order Travel the tree, Recursion:\n"); 
	}
	else
	{
		_tprintf_s(L"In Order Travel the tree, NON-Recursion:\n"); 

	}
	InorderTraversal(m_pRoot, bRecursion);
	_tprintf_s(L"\n");
}


template<typename T>
void CBinTree<T>::InorderTraversal(TreeNode<T>* pNode /* = m_pRoot */, bool bRecursion /*= true*/)
{
	if (NULL == pNode)
	{
		return;
	}
	if (bRecursion)
	{

		InorderTraversal(pNode->pLeftNode, bRecursion);
		DoVisit(pNode);
		InorderTraversal(pNode->pRightNode, bRecursion);
	}
	else
	{
		stack<TreeNode<T>*> St;
		St.push(pNode);
		bool bVisited = false;
		while(!St.empty())
		{
			//The first time,we just touch the node already in Stack
			//don't pop it out; because in the first time, we don't really visit this node . 
			TreeNode<T>* pCur = St.top(); 
			if (pCur)
			{
				if (pCur->pLeftNode && !bVisited)
				{
					St.push(pCur->pLeftNode);
				}
				else
				{
					//Now, we will visit the node and then pop it out of the stack
					DoVisit(pCur); 
					St.pop();
					bVisited = true;
					if (pCur->pRightNode)
					{
						St.push(pCur->pRightNode);
						bVisited = false;  //because in this case, the next loop will go into right subtree, it is the first time we touch right side.
					}
				}
			}

		}
	}
}


template<typename T>
void CBinTree<T>::PreorderTraversal(bool bRecursion /*= true*/)
{
	if (bRecursion)
	{
		_tprintf_s(L"Pre-Order Travel the tree, Recursion:\n"); 
	}
	else
	{
		_tprintf_s(L"Pre-Order Travel the tree, NON-Recursion:\n"); 

	}
	PreorderTraversal(m_pRoot, bRecursion);
	_tprintf_s(L"\n");
}


template<typename T>
void CBinTree<T>::PreorderTraversal(TreeNode<T> *pNode, bool bRecursion /*= true*/)
{
	if (NULL == pNode)
	{
		return;
	}
	if (bRecursion)
	{
		DoVisit(pNode);
		PreorderTraversal(pNode->pLeftNode, bRecursion);
		PreorderTraversal(pNode->pRightNode, bRecursion);
	}
	else
	{
		stack<TreeNode<T>*> St;
		St.push(pNode);
		while(!St.empty())
		{
			TreeNode<T>* pCur = St.top(); 
			St.pop();
			//Visit
			DoVisit(pCur);
			if (pCur->pRightNode)
			{
				St.push(pCur->pRightNode);
			}
			if (pCur->pLeftNode)
			{
				St.push(pCur->pLeftNode);
			}

		}
	}


}


template<typename T>
void CBinTree<T>::PostorderTraversal(bool bRecursion /*= true*/)
{
	if (bRecursion)
	{
		_tprintf_s(L"Post-Order Travel the tree, Recursion:\n"); 
	}
	else
	{
		_tprintf_s(L"Post-Order Travel the tree, NON-Recursion:\n"); 

	}
	PostorderTraversal(m_pRoot, bRecursion);
	_tprintf_s(L"\n");
}


template<typename T>
void CBinTree<T>::PostorderTraversal(TreeNode<T> *pNode, bool bRecursion /*= true*/)
{
	if (NULL == pNode)
	{
		return;
	}
	if (bRecursion)
	{
		PostorderTraversal(pNode->pLeftNode, bRecursion);
		PostorderTraversal(pNode->pRightNode, bRecursion);
		DoVisit(pNode);
	}
	else
	{
		stack<TreeNode<T>*> St;
		
		TreeNode<T>* pPre = NULL;
		TreeNode<T>* pCur = pNode;
		while(!St.empty() || pCur != NULL)
		{
			if (pCur)
			{
				St.push(pCur);
				pCur = pCur->pLeftNode;
			}
			else
			{
				//The first time,we just touch the node already in Stack
				//don't pop it out; because in the first time, we don't really visit this node . 
				pCur = St.top();
				if (pCur->pRightNode != NULL && pPre != pCur->pRightNode)
				{
				//	St.push(pCur->pRightNode);
					pCur = pCur->pRightNode;
				}
				else
				{
					DoVisit(pCur);
					St.pop(); // Now we should pop the top node out of the stack
					pPre = pCur;
					pCur = NULL;

				}

			}


		}

	}
}